//以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。 
//
// 在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成
//部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径 
//
// 请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表
//示绝对路径的最短字符串。 
//
// 
//
// 示例 1： 
//
// 输入："/home/"
//输出："/home"
//解释：注意，最后一个目录名后面没有斜杠。
// 
//
// 示例 2： 
//
// 输入："/../"
//输出："/"
//解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。
// 
//
// 示例 3： 
//
// 输入："/home//foo/"
//输出："/home/foo"
//解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。
// 
//
// 示例 4： 
//
// 输入："/a/./b/../../c/"
//输出："/c"
// 
//
// 示例 5： 
//
// 输入："/a/../../b/../c//.//"
//输出："/c"
// 
//
// 示例 6： 
//
// 输入："/a//b////c/d//././/.."
//输出："/a/b/c" 
// Related Topics 栈 字符串 
// 👍 188 👎 0

package leetcode.editor.cn;

import java.util.Iterator;
import java.util.Stack;

//Java：简化路径
public class P71SimplifyPath {

    /**
     *
     * 思路： 查找'/'位置，如果跟上一个'/'相连，就跳过，否则截取两个'/'之间的字符串str，判断str是'.'的话跳过，'..'的话，出栈(栈必须保留最底部的'/')，其他入栈。
     *      最后遍历栈，拼接目录间的'/'之后输出就是结果了
     *
     * 执行用时： 6 ms , 在所有 Java 提交中击败了 72.43% 的用户 内存消耗： 39.8 MB , 在所有 Java 提交中击败了 56.63% 的用户
     *
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String simplifyPath(String path) {
            Stack<String> stack = new Stack<>();
            stack.push("/");
            int lastSlash = 0;
            while (lastSlash < path.length() - 1 && lastSlash != -1) {
                int index = path.indexOf("/", lastSlash + 1);
                String str;

                if (index == -1) {
                    // 结尾了都没有 /
                    str = path.substring(lastSlash + 1, path.length());
                } else {
                    str = path.substring(lastSlash + 1, index);
                }

                // 连续的 '/'
                if (index - lastSlash == 1) {
                    lastSlash = index;
                    continue;
                }

                // 更新上一次斜杠位置
                lastSlash = index;

                switch (str) {
                    case ".":
                        break;
                    case "..":
                        if (stack.size() > 1) {
                            stack.pop();
                        }
                        break;
                    default:
                        stack.push(str);
                        break;
                }
            }

            Iterator<String> it = stack.iterator();
            StringBuilder sb = new StringBuilder("");
            while (it.hasNext()) {
                String n = it.next();
                sb.append(n);

                if(it.hasNext() && !"/".equals(n)){
                    sb.append("/");
                }
            }
            return sb.toString();
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new P71SimplifyPath().new Solution();
        System.out.println(solution.simplifyPath("/home/"));
        System.out.println(solution.simplifyPath("/../"));
        System.out.println(solution.simplifyPath("/home//foo/"));
        System.out.println(solution.simplifyPath("/a/./b/../../c/"));
        System.out.println(solution.simplifyPath("/a/../../b/../c//.//"));
        System.out.println(solution.simplifyPath("/a//b////c/d//././/.."));
        // TO TEST
    }

}